\relax 
\citation{DasSarmaNPT10}
\citation{IJ90}
\citation{BBF04}
\citation{CTW93}
\citation{KR04}
\citation{K00}
\citation{ZS06}
\citation{AHLP01}
\citation{C05}
\citation{GMS05}
\citation{LCCLS02}
\citation{BAS04}
\citation{KKD01}
\citation{GMS05}
\citation{LawS03}
\citation{LKRG03}
\citation{DT07}
\citation{Broder89}
\citation{BIZ89}
\citation{BFG+03}
\citation{MG07}
\citation{DSW06}
\citation{AKL+79}
\citation{LawS03}
\citation{GKM03}
\citation{ZSS05}
\citation{BBSB04}
\citation{ZS06}
\citation{BBSB04}
\citation{ZS06}
\citation{BBSB04}
\citation{ZS06}
\citation{DasSarmaNPT10}
\citation{DasSarmaNPT10}
\citation{DasSarmaNPT10}
\citation{DNP09-podc}
\@writefile{toc}{\contentsline {section}{\numberline {1}Introduction}{1}}
\citation{peleg}
\citation{PK09}
\citation{MG07}
\citation{GKM03}
\citation{MoralesGupta09}
\citation{MoralesGuptaTwo09}
\citation{AAKKLT}
\citation{LawS03}
\citation{DT07}
\citation{DT07}
\citation{Broder89}
\citation{Wilson96}
\citation{BIZ89}
\citation{GoyalRV09}
\@writefile{toc}{\contentsline {subsection}{\numberline {1.1}Distributed Network Model}{2}}
\@writefile{toc}{\contentsline {subsection}{\numberline {1.2}Related Work and Problem Statement}{2}}
\citation{DNP09-podc}
\citation{DasSarmaNPT10}
\citation{NanongkaiDP11}
\citation{DNP09-podc}
\citation{DNP09-podc}
\citation{DNP09-podc}
\citation{AtishGP08}
\citation{DNP09-podc}
\citation{AtishGP08}
\citation{DasSarmaNPT10}
\citation{DNP09-podc}
\citation{NanongkaiDP11}
\citation{DasSarmaNPT10}
\citation{DNP09-podc}
\citation{DasSarmaNPT10}
\citation{DasSarmaNPT10}
\citation{DasSarmaNPT10}
\@writefile{toc}{\contentsline {section}{\numberline {2}Theoretical Analysis of Algorithms}{4}}
\newlabel{sec:algos}{{2}{4}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.1}Algorithm descriptions}{4}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.2}Previous Results - Rounds and Messages}{4}}
\newlabel{thm:1-walk}{{2.1}{4}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {1}{\ignorespaces \sc  Pre-Processing($\eta $, $\lambda $)\relax }}{4}}
\providecommand*\caption@xref[2]{\@setref\relax\@undefined{#1}}
\newlabel{alg:pre-processing}{{1}{4}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {2}{\ignorespaces \sc  Single-Random-Walk($s$, $\ell $)\relax }}{5}}
\newlabel{alg:single-random-walk}{{2}{5}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {3}{\ignorespaces \sc  Continuous-Random-Walk($\ell $)\relax }}{5}}
\newlabel{alg:continuous-random-walk}{{3}{5}}
\newlabel{thm: message-1-walk}{{2.2}{5}}
\citation{DasSarmaNPT10}
\citation{DasSarmaNPT10}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.3}Round Complexity}{6}}
\newlabel{thm:round-multi-walk}{{2.3}{6}}
\newlabel{thm:avg-round}{{2.4}{6}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.4}Message Complexity}{6}}
\newlabel{thm:message-complexity1}{{2.5}{6}}
\newlabel{thm:avg-message-complexity}{{2.6}{6}}
\citation{MU-book-05}
\citation{NanongkaiDP11}
\newlabel{thm:combined-avg-complexity}{{2.7}{7}}
\newlabel{cor:avg-complexity}{{2.8}{7}}
\@writefile{toc}{\contentsline {section}{\numberline {3}Concentration Bounds on $\kappa $}{7}}
\newlabel{sec:conc}{{3}{7}}
\newlabel{thm:kappabound}{{3.1}{7}}
\citation{GkantsidisMS04}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.1}Extensions to different walk lengths}{8}}
\@writefile{toc}{\contentsline {section}{\numberline {4}Experiments}{8}}
\newlabel{sec:exp}{{4}{8}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.1}Short walk utilization factor $\kappa $}{9}}
\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces varying length of the walk $\ell $. $n=10K, \eta = 1, \lambda = \sqrt  {\ell }$\relax }}{10}}
\newlabel{fig:plot1c}{{1}{10}}
\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces varying number of nodes n. $\ell =n$, $\eta = 1, \lambda = \sqrt  {\ell }$\relax }}{10}}
\newlabel{fig:plot2}{{2}{10}}
\@writefile{lof}{\contentsline {figure}{\numberline {3}{\ignorespaces varying number of short walks $\eta $. $n = 10K, \ell =n, \lambda = \sqrt  {\ell }$\relax }}{11}}
\newlabel{fig:plot3}{{3}{11}}
\citation{DasSarmaNPT10}
\@writefile{lof}{\contentsline {figure}{\numberline {4}{\ignorespaces varying length of short walk $\lambda $. $n = 10K, \ell =n, \eta = \qopname  \relax o{log}n$\relax }}{12}}
\newlabel{fig:plot4}{{4}{12}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.2}Message complexity plots}{12}}
\@writefile{lof}{\contentsline {figure}{\numberline {5}{\ignorespaces varying length of the walk $\ell $. $n=10K, \eta = 1, \lambda = \sqrt  {\ell }$\relax }}{13}}
\newlabel{fig:Mplot1}{{5}{13}}
\@writefile{lof}{\contentsline {figure}{\numberline {6}{\ignorespaces varying number of nodes n. $\ell =$n, $\eta = \unhbox \voidb@x \hbox { logn },\lambda = \sqrt  {\ell }$\relax }}{13}}
\newlabel{fig:Mplot2}{{6}{13}}
\@writefile{lof}{\contentsline {figure}{\numberline {7}{\ignorespaces varying number of short walks $\eta $. $n = 10K, \ell =n, \lambda = \sqrt  {\ell }$\relax }}{14}}
\newlabel{fig:Mplot3}{{7}{14}}
\@writefile{lof}{\contentsline {figure}{\numberline {8}{\ignorespaces varying length of short walk $\lambda $. $n = 10K, \ell =n, \eta = \qopname  \relax o{log}n$\relax }}{14}}
\newlabel{fig:Mplot4}{{8}{14}}
\@writefile{toc}{\contentsline {section}{\numberline {5}Conclusion}{15}}
\newlabel{sec:conclusion}{{5}{15}}
\bibstyle{abbrv}
\bibdata{Distributed-RW}
\bibcite{AHLP01}{1}
\bibcite{AKL+79}{2}
\bibcite{AAKKLT}{3}
\bibcite{BFG+03}{4}
\bibcite{BIZ89}{5}
\bibcite{BBF04}{6}
\bibcite{BAS04}{7}
\bibcite{Broder89}{8}
\bibcite{BBSB04}{9}
\bibcite{C05}{10}
\bibcite{CTW93}{11}
\bibcite{AtishGP08}{12}
\bibcite{DNP09-podc}{13}
\bibcite{DasSarmaNPT10}{14}
\bibcite{DSW06}{15}
\bibcite{DT07}{16}
\bibcite{GKM03}{17}
\bibcite{GkantsidisMS04}{18}
\bibcite{GMS05}{19}
\bibcite{GoyalRV09}{20}
\bibcite{IJ90}{21}
\bibcite{KR04}{22}
\bibcite{KKD01}{23}
\bibcite{K00}{24}
\bibcite{LawS03}{25}
\bibcite{LKRG03}{26}
\bibcite{LCCLS02}{27}
\bibcite{MU-book-05}{28}
\bibcite{MG07}{29}
\bibcite{MoralesGupta09}{30}
\bibcite{MoralesGuptaTwo09}{31}
\bibcite{NanongkaiDP11}{32}
\bibcite{PK09}{33}
\bibcite{peleg}{34}
\bibcite{Wilson96}{35}
\bibcite{ZS06}{36}
\bibcite{ZSS05}{37}
